Read channel errors due to noise are rare. Estimating error probability at low noise levels involves selecting dominant error events (dominant trapping sets) and creating a reduced set of input test signals related to those trapping sets to reduce simulation time.
Low-density parity-check codes are linear codes with a sparse parity-check matrix. Sparse here means that the number of non-zero elements is a linear function of the size of the codewords.
It is known that decoding a low-density parity-check code on the binary symmetric channel is an NP-complete problem. So in order to ensure fast (linear) decoding, different techniques based on iterative belief propagation are used and give good approximations. But on the output of such iterative methods we can have words that are not codeword (because of the nature of belief propagation, the level of noise and so on), but some other word.
An output of such iterative methods which doesn't coincide with the original codeword may still be a valid codeword. This is a very bad situation for the decoder because the decoder does not have the ability to identify the valid but erroneous word. Hereafter such a situation will be called a miscorrection.
There exists a well-known technique called importance sampling, which is the modification of a Monte-Carlo method for the region which has the biggest error probability. One of the applications of the importance sampling method for finding low error rates (having the small level of noise) is the Cole method presented in a paper by Cole et al (a general method for finding low error rates of low-density parity-check codes) hereby incorporated by reference. The Cole method deals with so-called trapping sets (or near codewords), i.e. Some words, which are not codewords but can be converted to codewords with small effort, and leading to errors in case of small levels of noise. A trapping set is a set of variable nodes that produce a sub-graph of the tanner graph having special properties that cause error conditions in the decoder. Trapping sets depend on the decoder's parity check matrix, and on the decoding algorithm, and are mostly unknown for real-life decoders until determined experimentally.
The Cole method is a generalized method for finding low error rate low-density parity-check codes. The first step of the Cole method performs a search for potentially problematic trapping sets. The second step of the Cole method is used to select dominant (i.e. having more impact on probability of error) trapping sets from a list obtained in the first step. Considering a segment in a graph with the codeword on the left terminus and a given trapping set on the right terminus; movement along the segment is controlled by varying the amplitude of specially injected noise. The second step of the Cole method finds a critical noise level (resulted in squared error boundary distance) using a binary search along the segment. At a particular noise level, the critical noise level is moved to the right if the codeword is correctly decoded and to the left if the codeword is decoded as the trapping set. So, if the amplitude of the noise is greater than the critical level then the decoder gets the trapping set with a fairly high probability. The importance of the given trapping set for an original codeword corresponds to the distance from the original code word to a critical point on the segment. The third step runs importance sampling simulations by estimating error probability density functions for each trapping set when injecting noise of a certain level in a direction towards the trapping set; integrating the probability density over all injection levels; and summing up all integral probabilities taking trapping set multiplicity coefficients into account.
The Cole method is formulated for use in additive white Gaussian noise channels. In additive white Gaussian noise channels the resulting error boundary distance does not depend on the original codeword located at the left point of the corresponding segment: instead, we can consider any valid codeword that satisfies the linearity requirement on the left and the product of an exclusive disjunction operation of the codeword and trapping set on the right. This can be explained by variable independence in Gaussian noise channel and linear properties of low-density parity-check code.
Unlike additive white Gaussian noise channel there exist a variety of other channel types with ISI (inter symbol interference) like PR (partial response) or jitter channels. For these channels the second step of the Cole method will give significantly different estimations of error boundary distance for different random codewords. These non-stationary features of such channels require considering a set of randomly chosen original codewords. For this type of channel, even traditional importance sampling technique is ineffective because the number of simulations needed to get reliable error rate estimations is increased by several orders of magnitude as compared to average error rate results over different random input sectors. Furthermore, in real life, noise channels are usually data dependent.
The error floor phenomenon is related to all iterative decoding of low-density parity-check codes. It was discovered that the error floors under message-passing iterative decoding are usually due to low-weight trapping sets rather than low-weight codewords. Another (more rare) type of errors is related to miscorrection events mentioned above. For data-dependent noise channels we have discovered that there are classes of codewords that provoke additional errors of the decoder. Selecting such a “dominant” codeword class increase the error rate more significantly than selecting a dominant trapping set class.
Estimating probability of error could be made by running a direct simulation. But considering the real levels of error for high signal-to-noise ratios in modern hard disk drives, there is no possibility to get a real error probability estimation in a reasonable time.
Consequently, it would be advantageous if an apparatus existed that is suitable for estimating error probability of given low-density parity-check codes in a particular channel model.